Most Complex Deterministic Union-Free Regular Languages

摘要

A regular language $L$ is union-free if it can be represented by a regularexpression without the union operation. A union-free language is deterministicif it can be accepted by a deterministic one-cycle-free-path finite automaton;this is an automaton which has one final state and exactly one cycle-free pathfrom any state to the final state. Jir\'askov\'a and Masopust proved that thestate complexities of the basic operations reversal, star, product, and booleanoperations in deterministic union-free languages are exactly the same as thosein the class of all regular languages. To prove that the bounds are met theyused five types of automata, involving eight types of transformations of theset of states of the automata. We show that for each $n\ge 3$ there exists oneternary witness of state complexity $n$ that meets the bound for reversal andproduct. Moreover, the restrictions of this witness to binary alphabets meetthe bounds for star and boolean operations. We also show that the tight upperbounds on the state complexity of binary operations that take arguments overdifferent alphabets are the same as those for arbitrary regular languages.Furthermore, we prove that the maximal syntactic semigroup of a union-freelanguage has $n^n$ elements, as in the case of regular languages, and that themaximal state complexities of atoms of union-free languages are the same asthose for regular languages. Finally, we prove that there exists a most complexunion-free language that meets the bounds for all these complexity measures.Altogether this proves that the complexity measures above cannot distinguishunion-free languages from regular languages.